package algorithm;

import java.util.LinkedList;

public class LeetCodeTest2 {

    public static int[] getMaxWindow(int[] arr, int w) {
        if (arr == null || w < 1 || arr.length < w) {
            return null;
        }
        // 双端队列  从大到小存储，存储的是数组的索引
        LinkedList<Integer> qMax = new LinkedList<>();
        int[] res = new int[arr.length - w + 1];
        int index = 0;
        for (int i = 0; i < arr.length; i++) {
            // 遇到大于等于队尾的，队尾出队
            while(!qMax.isEmpty() && arr[qMax.peekLast()] <= arr[i]) {
                qMax.pollLast();
            }
            qMax.addLast(i);
            // 队首出队：当窗口往右移一步，则队首的index不在窗口内，则出队
            if (qMax.peekFirst() == i - w) {
                qMax.pollFirst();
            }
            // 假设w==3，则当索引到了2时开始保存当前窗口的最大值
            if (i >= w -1) {
                res[index++] = arr[qMax.peekFirst()];
            }
        }

        return res;
    }

    public static void main(String[] args) {

    }
}
